package 面试常见刷题;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class 桶排序 {
    public static void main(String[] args) {
        int[] ints = {1, 213, 12, 31, 41, 12};
        int[] ans = bucketSort(ints,2);
        System.out.println(Arrays.toString(ans));
    }

    private static int[] bucketSort(int[] data, int bucketSize) {
        int[] ans = new int[data.length];
        if(data.length<2) return data;
        int min = 1<<30,max = -1<<30;
        for (int datum : data) {
            if(min>datum){
                min = datum;
            }
            if(max<datum) {
                max = datum;
            }
        }
        int bucketNum = (max-min)/bucketSize+1;
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int datum : data) {
            buckets.get((datum-min)/bucketSize).add(datum);
        }
        final int[] index = {0};
        buckets.forEach(l->{
            l.sort(Integer::compareTo);
            for (Integer integer : l) {
                ans[index[0]++] = integer;
            }
        });
        return ans;
    }
}
